package algorithm.dynamicProgramming.p300;

import java.util.Arrays;

/**
 * @Author CandyWall
 * @Date 2021/4/6--20:34
 * @Description
 */
public class Solution_v2 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        // memo[i]表示以nums[i]为结尾的最长上升子序列的长度
        int[] memo = new int[nums.length];
        Arrays.fill(memo, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 检查i之前的元素是否跟i构成最小子序列
                if (nums[j] < nums[i]) {
                    memo[i] = Math.max(memo[i], memo[j] + 1);
                }
            }
        }

        int res = 1;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, memo[i]);
        }

        return res;
    }
}
